package genetic;



import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public abstract class Phenotype {

	public abstract Genotype makeInstanceFromTree(TreeNode tree);
	public abstract double fitness(Genotype g);
	public abstract Genotype[] crossover(Genotype g1, Genotype g2);
	public abstract Genotype mutate(Genotype g);
	public abstract Genotype[] selectParents(List<Genotype> population,	int populationSize);
	public abstract void updateFitness(List<Genotype> population);
	public abstract List<Genotype> getInitialPopulation(int populationSize);
	public abstract void doEvery50(List<Genotype> population);

	List<Function> functions;
	List<Terminal> terminals;

	public Phenotype() {
	}

	public void init(List<Function> functions, List<Terminal> terminals) {
		this.functions = functions;
		this.terminals = terminals;
	}

	public List<Genotype> getInitialPopulationCommon(int populationSize, int dmax){
		List<Genotype> ans = new LinkedList<Genotype>();
		for (int i=0; i<populationSize; i++){
			TreeNode tmp;
			if (i%2==0) tmp = growFullRandomTree(dmax);
			else tmp = growRandomTree(dmax);
			tmp.updateTotalKids();
			ans.add(makeInstanceFromTree(tmp));
		}
		return ans;
	}


	public TreeNode growRandomTree(int dmax){
		int rand;
		TreeNode root;
		if (dmax==1){
			rand = (int)(Math.random()*(terminals.size()));
		} else {
			rand = (int)(Math.random()*(terminals.size()+functions.size()));
		}
		if (rand<terminals.size()){
			root = terminals.get(rand);
		} else {
			Function f = functions.get(rand-terminals.size());
			TreeNode[] kids = new TreeNode[f.getNumKids()];
			for (int i=0; i<kids.length; i++){
				kids[i] = growRandomTree(dmax-1);
			}
			root = f.createRandomInstance(kids);
		}
		return root;
	}

	public TreeNode growFullRandomTree(int dmax){
		int rand;
		TreeNode root;
		if (dmax==1){
			rand = (int)(Math.random()*(terminals.size()));
			root = terminals.get(rand);
		} else {
			rand = (int)(Math.random()*(functions.size())) + terminals.size();
			Function f = functions.get(rand-terminals.size());
			TreeNode[] kids = new TreeNode[f.getNumKids()];
			for (int i=0; i<kids.length; i++){
				kids[i] = growFullRandomTree(dmax-1);
			}
			root = f.createRandomInstance(kids);
		}
		return root;
	}

	public Genotype mutateDefault(Genotype g, int dmax){
		Genotype gn = g.clone();
		TreeNode t = gn.getTree();
		ReplaceInfo subTree = selectRandomFromTree(t);
		TreeNode child = growRandomTree(dmax);
		if (subTree.f == null){
			gn.setTree(child);
		} else {
			subTree.f.replaceChild(child, subTree.index);
		}
		gn.getTree().updateTotalKids();
		return gn;
	}

	public Genotype[] crossoverDefault(Genotype g1, Genotype g2, int type){
		Genotype gn1 = g1.clone();
		Genotype gn2 = g2.clone();
		TreeNode t1 = gn1.getTree();
		TreeNode t2 = gn2.getTree();

		//carmel
		gn1.setTreeIndexes();
		gn2.setTreeIndexes();

		ReplaceInfo subTree1;// = selectRandomFromTree(t1);
		ReplaceInfo subTree2;// = selectRandomFromTree(t2);

		if (type==0){
			subTree1 = selectRandomFromTree(t1);
			subTree2 = selectRandomFromTree(t2);
		} else {
			subTree1 = selectRandomFromTreeUsingIndexes(t1);
			subTree2 = selectRandomFromTreeByDepth(subTree1.depth, t2);
		}

		if (subTree1.f == null && subTree2.f == null){
			gn1.setTree(t2.clone());
			gn2.setTree(t1.clone());
		} else {
			if (subTree1.f == null){
				gn1.setTree(subTree2.f.clone());
			} else {
				if (subTree2.f == null){
					subTree1.f.replaceChild(t2.clone(), subTree1.index);
				} else {
					subTree1.f.replaceChild(subTree2.f.clone(), subTree1.index);
				}
			}
			if (subTree2.f == null){
				gn2.setTree(subTree1.f.clone());
			} else {
				if (subTree1.f == null){
					subTree2.f.replaceChild(t1.clone(), subTree2.index);
				} else {
					subTree2.f.replaceChild(subTree1.f.clone(), subTree2.index);
				}
			}
		}
		gn1.getTree().updateTotalKids();
		gn2.getTree().updateTotalKids();
		return new Genotype[]{gn1, gn2};
	}

	public Genotype[] crossover2(Genotype g1, Genotype g2){
		Genotype gn1 = g1.clone();
		Genotype gn2 = g2.clone();
		TreeNode t1 = g1.getTree();
		TreeNode t2 = g2.getTree();
		ReplaceInfo subTree1 = selectRandomFromTree(gn1.getTree());
		ReplaceInfo subTree2 = selectRandomFromTree(t2);
		if (subTree1.f == null && subTree2.f == null){
			gn1.setTree(t2.clone());
		} else {
			if (subTree1.f == null){
				gn1.setTree(subTree2.f.clone());
			} else {
				if (subTree2.f == null){
					subTree1.f.replaceChild(t2.clone(), subTree1.index);
				} else {
					subTree1.f.replaceChild(subTree2.f.clone(), subTree1.index);
				}
			}
		}
		subTree1 = selectRandomFromTree(t1);
		subTree2 = selectRandomFromTree(gn2.getTree());
		if (subTree1.f == null && subTree2.f == null){
			gn2.setTree(t1.clone());
		} else {
			if (subTree2.f == null){
				gn2.setTree(subTree1.f.clone());
			} else {
				if (subTree1.f == null){
					subTree2.f.replaceChild(t1.clone(), subTree2.index);
				} else {
					subTree2.f.replaceChild(subTree1.f.clone(), subTree2.index);
				}
			}
		}
		gn1.getTree().updateTotalKids();
		gn2.getTree().updateTotalKids();
		return new Genotype[]{gn1, gn2};
	}

	private static class ReplaceInfo{
		Function f;
		int index;
		int depth = 0;
		public ReplaceInfo(Function f, int index) {
			this.f = f;
			if(f!=null){
				this.depth = f.depth+1;
			}
			this.index = index;
		}
	}

	//helping functions
	public ReplaceInfo selectRandomFromTree(TreeNode tree){
		int numKids = tree.getTotalNumKids();
		//		if (numKids==0) return new ReplaceInfo(null, 0);

		int rand = (int)(Math.random()*numKids);

		TreeNode[] kids = new TreeNode[]{tree};
		int index = 0;
		TreeNode parent = null;

		//		System.out.println(rand + "/"+numKids);
		//		System.out.println(rand);
		while (rand>0){
			parent = kids[index];
			if (parent.isFunction()){
				kids = ((Function)parent).getKids();
				int num = 0;
				for (int i=0; i<kids.length && num<rand; i++){
					rand = rand-num;
					num = 1 + kids[i].getTotalNumKids();
					index = i;
				}
				rand--;
			} else {
				//				System.out.println("ERROR " + rand + " - " + parent + " : " + index);
			}
		}
		return new ReplaceInfo(((Function)parent), index);
	}

	//helping functions
	public ReplaceInfo selectRandomFromTreeUsingIndexes(TreeNode tree){
		int numKids = tree.getTotalNumKids();
		//		if (numKids==0) return new ReplaceInfo(null, 0);


		int rand = (int)((Math.random()*numKids)+1);

		if (!tree.isFunction()){
			return new ReplaceInfo(null, 0);
		}

		TreeNode[] kids = ((Function)tree).getKids();
		TreeNode parent = null;

		if (rand==0)
			return new ReplaceInfo(((Function)parent), 0);


		for (int i=0; i < kids.length; i++){
			if(kids[i].getID()==rand){
				parent = tree;
				return new ReplaceInfo(((Function)parent), i);
			}else if(i<kids.length-1 && kids[i+1].getID()>rand){
				return selectRandomIteration(kids[i], rand);
			}else if(i==kids.length-1){
				return selectRandomIteration(kids[i], rand);
			}
		}
		return null;
	}

	private ReplaceInfo selectRandomIteration(TreeNode tree, int rand) {
		if(0==rand){
			return new ReplaceInfo(null, 0);
		}
		TreeNode[] kids = ((Function)tree).getKids();
		TreeNode parent = tree;

		for (int i=0; i < kids.length; i++){
			if(kids[i].getID()==rand){
				parent = tree;
				return new ReplaceInfo(((Function)parent), i);
			}else if(i<kids.length-1 && kids[i+1].getID()>rand){
				return selectRandomIteration(kids[i], rand);
			}else if(i==kids.length-1){
				return selectRandomIteration(kids[i], rand);
			}
		}
		return null;
	}

	private ReplaceInfo selectRandomFromTreeByDepth(int depth, TreeNode tree) {
		Vector<Integer> indexes = new Vector<Integer>();
		if (!tree.isFunction()){
			return new ReplaceInfo(null, 0);
		}
		TreeNode[] kids = ((Function)tree).getKids();

		if((depth-2 <tree.depth) && (tree.depth < depth+1)){
			indexes.add(tree.id);
			for (TreeNode t: kids){
				selectRandomFromTreeByDepth(depth,t, indexes);
			}

		}else if(tree.depth == depth+1){
			indexes.add(tree.id);
		}else{
			for (TreeNode t: kids){
				selectRandomFromTreeByDepth(depth,t, indexes);
			}
		}
		int rand = (int)(Math.random()*indexes.size());
		return selectRandomIteration(tree, indexes.elementAt(rand));
	}

	private void selectRandomFromTreeByDepth(int depth, TreeNode tree,
			Vector<Integer> indexes) {
		if (tree.isFunction()){
			TreeNode[] kids = ((Function)tree).getKids();
			if((depth-2 <tree.depth) && (tree.depth < depth+1)){
				indexes.add(tree.id);
				for (TreeNode t: kids){
					selectRandomFromTreeByDepth(depth,t, indexes);
				}

			}else if(tree.depth == depth+1){
				indexes.add(tree.id);
			}else{
				for (TreeNode t: kids){
					selectRandomFromTreeByDepth(depth,t, indexes);
				}
			}
		} else {
			if((depth-2 <tree.depth) && (tree.depth < depth+2)){
				indexes.add(tree.id);
			}
		}

	}
	//goes down the tree with given probability, or returns the node
	//returns a terminal if getting to one
	public TreeNode selectRandomFromTree(TreeNode tree, double prob){
		TreeNode[] kids = new TreeNode[]{tree};
		int index = 0;
		TreeNode position = tree;
		while (Math.random() < prob){
			if (kids[index].isFunction()){
				position = kids[index];
				index = (int)(Math.random()*((Function)position).getNumKids());
				kids = ((Function)position).getKids();
			}
		}
		return position;
	}


	//	private int indexOf(int[] arr, int num){
	//		for (int i=0; i<arr.length; i++){
	//			if (arr[i] == num) return i;
	//		}
	//		return -1;
	//	}
	//
	//	//returns 2 random numbers, between a given range, and with offset between each other.
	//	protected int[] getRandomPair(int size){
	//		return getRandomPair(size, 1, size);
	//	}
	//
	//	protected int[] getRandomPair(int size, int minoffset){
	//		return getRandomPair(size, minoffset, size);
	//	}
	//
	//	protected int[] getRandomPair(int size, int minoffset, int maxoffset){
	//		int rand1 = (int)(Math.random()*(double)(size-minoffset));
	//		int rand2 = (int)(Math.random()*(double)(Math.min(maxoffset, size-(rand1+minoffset)))) + rand1+minoffset;
	//		return new int[]{rand1, rand2};
	//	}

	protected Genotype[] selectMatingParentsRouletteWheel(List<Genotype> population, int populationSize){	//TODO rounding is needed to overcome double errors
		Genotype[] ans = new Genotype[2];

		double fitnessSum = 0;
		for (Genotype g: population){
			fitnessSum = fitnessSum + fitness(g);
		}
		for (int i=0; i<2; i++){	//creating the mating pool
			double rand = Math.random()*fitnessSum;
			for (Genotype g: population){
				rand = rand - fitness(g);
				if (rand<=0){
					ans[i] = g;
					break;
				}
			}
		}
		return ans;
	}

	protected Genotype[] selectMatingPoolTournamentSelection(List<Genotype> population, int populationSize, int tournamentSize, int numWinners, double p){	//TODO rounding is needed to overcome double errors
		Genotype[] ans = new Genotype[2];

		Vector<Genotype> tournament = new Vector<Genotype>();
		for (int i=0; i<tournamentSize; i++){
			int index = (int)(Math.random()*(double)populationSize);
			tournament.add(population.get(index));
		}

		Collections.sort(tournament, new Comparator<Genotype>(){
			public int compare(Genotype o1, Genotype o2) {
				if (fitness(o1) > fitness(o2)){
					return -1;
				} else if (fitness(o1) < fitness(o2)){
					return 1;
				} else {
					return 0;
				}
			}
		});

		for (int i=0; i<2; i++){
			for (int j=0; j<tournament.size(); j++){
				if (Math.random()<p || j == tournament.size()-1){
					ans[i] = tournament.remove(j);
					break;
				}
			}
		}
		return ans;
	}

	protected Genotype[] selectMatingPoolTournamentSelection2(List<Genotype> population, int populationSize, int tournamentSize, int numWinners, double p){	//TODO rounding is needed to overcome double errors
		Genotype[] ans = new Genotype[2];

		for (int k=0; k<2; k++){
			Vector<Genotype> tournament = new Vector<Genotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}

			Collections.sort(tournament, new Comparator<Genotype>(){
				public int compare(Genotype o1, Genotype o2) {
					if (fitness(o1) > fitness(o2)){
						return -1;
					} else if (fitness(o1) < fitness(o2)){
						return 1;
					} else {
						return 0;
					}
				}
			});

			for (int j=0; j<tournament.size(); j++){
				if (Math.random()<p || j == tournament.size()-1){
					ans[k] = tournament.remove(j);
					break;
				}
			}
		}
		return ans;
	}

	protected Genotype[] selectMatingPoolTournamentSelection3(List<Genotype> population, int populationSize, int tournamentSize){	//TODO rounding is needed to overcome double errors
		Genotype[] ans = new Genotype[2];

		for (int k=0; k<2; k++){
			Vector<Genotype> tournament = new Vector<Genotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}
			double fitness = -10000000;
			int spot = 0;
			for (int j=0; j<tournament.size(); j++){
				if (fitness(tournament.elementAt(j)) > fitness){
					spot = j;
				}
			}
			ans[k] = tournament.remove(spot);
		}
		//		System.out.println("ans[0] "+ans[0]);
		//		System.out.println("ans[1] "+ans[1]);
		return ans;
	}

	protected Genotype[] selectMatingPoolTournamentSelection4(List<Genotype> population, int populationSize, int tournamentSize){	//TODO rounding is needed to overcome double errors
		Genotype[] ans = new Genotype[2];

		for (int k=0; k<2; k++){
			Vector<Genotype> tournament = new Vector<Genotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}
			double fitness = Double.MAX_VALUE;
			int spot = 0;
			for (int j=0; j<tournament.size(); j++){
				if (fitness(tournament.elementAt(j)) < fitness){
					spot = j;
				}
			}
			ans[k] = tournament.remove(spot);
		}
		//		System.out.println("ans[0] "+ans[0]);
		//		System.out.println("ans[1] "+ans[1]);
		return ans;
	}

	//TODO over-selection(page 19)

	public static void main(String[] args) {
		Vector<Integer> i = new Vector<Integer>();
		i.add(0);
		i.add(5);
		i.add(0);
		i.add(4);
		i.add(2);
		i.add(3);
		i.add(19);
		System.out.println(i);
		Collections.sort(i, new Comparator<Integer>(){
			public int compare(Integer o1, Integer o2) {
				if (o1 < o2) {
					return -1;
				} else if (o2 < o1){
					return 1;
				} else {
					return 0;
				}
			}

		});
		System.out.println(i);
	}
	
	public List<Function> getFunctions(){
		return functions;
	}
	
	public List<Terminal> getTerminals(){
		return terminals;
	}
}
